#include <bits/stdc++.h>

using namespace std;

int shortestPathBinaryMatrix(vector<vector<int>>& grid);
void check_push(array<int, 2> point, deque<array<int, 2>>& queue, set<array<int, 2>>& vis);

class Solution {
public:
	void check_push(array<int, 2> point, deque<array<int, 2>>& queue, set<array<int, 2>>& vis)
	{
		if (vis.count(point))
			return;
		vis.insert(point);
		queue.push_back(point);
	}

	int shortestPathBinaryMatrix(vector<vector<int>>& grid)
	{
		if (grid[0][0])
			return -1;

		deque<array<int, 2>> queue { { 0, 0 } };
		array<int, 2> last = { 0, 0 };

		set<array<int, 2>> vis;
		vis.insert(last);

		int res = 1;
		while (!queue.empty()) {
			auto pop = queue.front();
			queue.pop_front();

			int row = pop[1], col = pop[0];
			if (col == grid.size() - 1 && row == grid[0].size() - 1 && !grid[col][row])
				return res;
			if (col > 0) {
				if (!grid[col - 1][row])
					check_push({ col - 1, row }, queue, vis);
				if (row > 0 && !grid[col - 1][row - 1])
					check_push({ col - 1, row - 1 }, queue, vis);
				if (row < grid[0].size() - 1 && !grid[col - 1][row + 1])
					check_push({ col - 1, row + 1 }, queue, vis);
			}
			if (row > 0 && !grid[col][row - 1])
				check_push({ col, row - 1 }, queue, vis);
			if (col < grid.size() - 1) {
				if (!grid[col + 1][row])
					check_push({ col + 1, row }, queue, vis);
				if (row > 0 && !grid[col + 1][row - 1])
					check_push({ col + 1, row - 1 }, queue, vis);
				if (row < grid[0].size() - 1 && !grid[col + 1][row + 1])
					check_push({ col + 1, row + 1 }, queue, vis);
			}
			if (row < grid[0].size() - 1 && !grid[col][row + 1])
				check_push({ col, row + 1 }, queue, vis);

			if (pop == last) {
				res++;
				last = queue.back();
			}
		}

		return -1;
	}
};

int main()
{
	Solution solu;
	vector<vector<int>> grid = { { 0, 1 }, { 1, 0 } };
	solu.shortestPathBinaryMatrix(grid);
	return 0;
}
